The latter half of the twentieth century has been witness to a phenomenon known as the information revolution. While the information revolution is a historical development broader in scope than any one event or machine, no single device has come to represent the information revolution more than the digital electronic computer. The development of computer systems has surely been a revolution. Each year, computer systems grow faster, store more data, and provide more applications to their users.
The extensive data storage needs of modem computer systems require large capacity mass data storage devices. While various data storage technologies are available, the rotating magnetic rigid disk drive has become by far the most ubiquitous. Such a disk drive data storage device is an extremely complex piece of machinery, containing precision mechanical parts, ultra-smooth disk surfaces, high-density magnetically encoded data, and sophisticated electronics for encoding/decoding data, and controlling drive operation. Each disk drive is therefore a miniature world unto itself, containing multiple systems and subsystem, each one of which is needed for proper drive operation. Despite this complexity, rotating magnetic disk drives have a proven record of capacity, performance and cost which make them the storage device of choice for a large variety of applications.
A disk drive typically contains data recorded in multiple sectors located on concentric tracks on the surface of one or more flat disks, which rotate at a constant speed. In order to access data (read data from the disk or write data to the disk), a moveable actuator positions a transducer adjacent a desired data track. The drive then waits until the disk rotates to an angular position in which the desired data sector is directly adjacent the transducer. The time required for the disk drive to execute any given data access operation therefore includes the time required to move the actuator from its current position to the desired track position (referred to as a seek) and the time required to wait until the disk rotates to the desired angular position (referred to as latency). The execution time also includes the time required to actually read or write the data once the actuator is properly positioned, but experience has shown that for many operating environments, the amount of data accessed in each operation is relatively small, and that the seek and latency times are more significant than the time required to read or write the data.
In order to keep up with advances in other areas of digital data processing technology, disk drive storage devices must make continual improvements in performance, reliability and data capacity. Performance may be measured as the average number of data access operations per unit time, which depends on the average seek time and average latency time. Seek time can be reduced by designing faster, more powerful actuators and latency can be reduced by spinning the disk at a higher velocity, but there are design constraints which impose practical limits to the improvements that can be obtained by these means.
For a given mechanical design and data formatting, it is possible to obtain still further improvement by intelligently ordering the data access operations. Specifically, it will be observed that the seek time and latency time for a given data access operation are not absolute, but are dependent, among other things, on the current position of the actuator (which affects the length of the seek) and current angular position of the disk (which affects latency). Typically, multiple data access operations are enqueued in an internal command buffer in the disk drive. By intelligently selecting the order of execution of these data access operations, it is possible to choose operations such that the average seek and access times are reduced. Thus, although the actuator speed and other characteristics are not changed, the average seek time is reduced because operations are ordered such that the average length of the seek is reduced. Similarly, although the rotational speed of the disk is not changed, the average latency is reduced because operations are ordered such that, after completing the seek, the average angle of rotation of the disk until reaching the desired data is reduced.
Various techniques have been used to take advantage of these characteristics by intelligently selecting the order of execution of enqueued data access operations. In general, these algorithms estimate, for each of multiple enqueued data access operations, the amount of time required for seek and latency from the actuator position at the end of an Nth access operation to the beginning of the enqueued data access operation, and select one of the enqueued data access operations for execution as the (N+1)th operation on the basis of these estimates.
Optimal performance of the ordering algorithm depends on the accuracy of the estimates, and in particular, the accuracy of the seek time estimate. If the seek time estimate is too low, the algorithm may select a data access operation for which the actuator can not settle on the desired track in time, causing the actuator to wait a full revolution of the disk on the track until the desired data is available. If the seek time estimate is too high, the algorithm will reject some operations having very little latency but which could have been performed in favor of slower operations having greater latency after the seek.
Obtaining accurate seek time estimates is difficult because seek time is dependent on so many variables, and the required speed of disk drive operation means that any seek estimation technique must execute very rapidly. Conventional algorithms have estimated seek time based on the length of seek and whether the next operation is a read or a write (the write generally requiring greater track following accuracy, and hence a longer seek time before settling on the track). But other factors may affect seek time. Actuator speeds (and hence seek time) are not necessarily the same for all radial zones of the disk or for both seek directions. Normal manufacturing process variations in each individual head, actuator, disk, and other components mean that the seek time characteristics will not only vary from one disk drive device to another of the same model and manufacturer, but that even within a single drive, the seek time characteristics will vary from one data recording surface to another. Moreover, seek time within any particular drive can change as the drive ages, or as the temperature varies.
A need exists for improved techniques for scheduling data access operations, and in particular, for improved techniques for estimating seek time of multiple enqueued data access operations.